<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>二分查找</title>
  </head>
  <body></body>
  <script>
    // 二分查找，也称为折半查找，是指在有序的数组里找出指定的值，返回该值在数组中的索引。
    // 查找步骤如下：
    // 1. 将数组折半，分成左右两个数组。
    // 2. 判断要查找的数和中间位置数值的大小，来判断要查找的数实在哪一半。
    // 3. 之后继续折半查找，直至找到这个数
    // 二分查找的优点和缺点
    // 优点是比较次数少，查找速度快，平均性能好；
    // 其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
    // 数组必须是有序数组
    var arr = [0, 13, 21, 35, 46, 52, 68, 77, 89, 94];
    function search(arr, key) {
      // 初始索引开始位置和结束位置
      var start = 0,
        end = arr.length - 1;
      while (start <= end) {
        // mid 是 取上限和下限中间的索引
        var mid = parseInt((end + start) / 2);
        if (key == arr[mid]) {
          // 如果找到则直接返回
          return mid;
        } else if (key > arr[mid]) {
          // 如果key是大于数组中间索引的值则将索引开始位置设置为中间索引+1
          start = mid + 1;
        } else {
          // 如果key是小于数组中间索引的值则将索引结束位置设置为中间索引-1
          end = mid - 1;
        }
      }
      // 如果在循环内没有找到查找的key(start<=end)的情况则返回-1
      return -1;
    }
    console.log(search(arr, 68));
  </script>
</html>
